#include <iostream>
#include <cstdlib>
#include <climits>
#define INF 100000

using namespace std;

int resp = 100000;

/*
	imprime matriz
	parametros:
		m - matriz
		tam - tamanho da matriz
*/
void imprime_matriz(int **m, int tam){
	for (int i = 0; i < tam; ++i){
		/* code */
		for (int j = 0; j < tam; ++j){
			/* code */
			cout << m[i][j];
			cout << " \t";
		}
		cout << endl;
	}
}



/* dijskra */
/*
	resolve o problema de caminho minimo dado um ponto de origem
	parametros:
		mAdj - matriz de adjacencias (grafo)
		njuncoes - numero de vertices (juncoes)
		ini - ponto inicial
*/
int* dijskra(int **mAdj, int njuncoes, int ini){


	// cout << "Dijsktra-----------inicio:" << ini+1 << "-------" << endl;

	/* vetor que verifica vertice visitado */
	int *v = (int*) calloc (njuncoes , sizeof(int));
	/* vetor que indica os caminhos minimos do vertice inicial*/
	int *d = (int*) malloc (njuncoes * sizeof(int));

	/* inicializa com infinito */
	for (int i = 0; i < njuncoes; ++i){
		d[i] = INF;
	}

	int valPrev = 0;	/* previous value */
	int currPos = ini;	/* valor inicial */
	int nextPos, nextVal = INF;
	int temp;
	int resp1 = 0;

	d[currPos] = 0;
	for (int i = 0; i < njuncoes; ++i){
		/* code */

		v[currPos] = 1;	/* indica que o vertice atual foi visitado */
		for (int j = 0; j < njuncoes; ++j){
			/* code */
			temp = mAdj[currPos][j];
			if(temp + valPrev <= d[j]){
				d[j] = temp + valPrev;
			}
			if(d[j] <= nextVal && v[j] == 0){
					nextPos = j;
					nextVal = d[j];
				}
		}
		currPos = nextPos;
		valPrev = d[nextPos];
		nextVal = INF;

/*		cout << "iteracao " << i << " -- ";
		for (int i = 0; i < njuncoes; ++i)
			cout << " " << d[i];
		cout << endl;*/
	}
	// cout << endl;

	free(v);

	return d;
}

void imprime_resultado(int **m, int tam){
	int col,lin;
	lin = INF;
	for (int i = 0; i < tam; ++i){
		col = 0;
		for (int j = 0; j < tam; ++j){
			if(m[i][j] > col)
				col = m[i][j];
		}
		if (col < lin){
			lin = col;
		}
	}
	cout << "R: " << lin << endl;
	return;
}



int main(int argc, char const *argv[]){
	/* code */
	unsigned int njuncoes, nruas;
	int ini, dest, val;
	int **mAdj, **mCam;
	int *aux;

	cin >> njuncoes;
	cin >> nruas;

	mAdj = (int**) malloc (njuncoes * sizeof(int*));
	mCam = (int**) malloc (njuncoes * sizeof(int*));
	// aux = (int *) malloc (njuncoes * sizeof(int));

	for (int i = 0; i < njuncoes; ++i){
		/* code */
		mAdj[i] = (int*) malloc (njuncoes * sizeof(int));
		mCam[i] = (int*) malloc (njuncoes * sizeof(int));
	}

	for (int i = 0; i < njuncoes; ++i){
		/* code */
		for (int j = 0; j < njuncoes; ++j){
			/* code */
			mAdj[i][j] = INF;
			mCam[i][j] = INF;
			if (i == j){
				mAdj[i][j] = 0;
				mCam[i][j] = 0;
			}
		}
	}

	for (int i = 0; i < nruas; ++i){
		/* code */
		cin >> ini;
		cin >> dest;
		cin >> val;
		mAdj[dest-1][ini-1] = mAdj[ini-1][dest-1] = val;
	}


	#pragma omp parallel for shared(mAdj)
	for (int i = 0; i < njuncoes; ++i){
		/* code */
		mCam[i] = dijskra(mAdj,njuncoes,i);
	}


	/*cout << "Matriz Adj----------------" << endl;
	imprime_matriz(mAdj, njuncoes);
	cout << endl << "Matriz Caminhos minimos------------------" << endl;
	imprime_matriz(mCam, njuncoes);
*/
	imprime_resultado(mCam, njuncoes);

	free(mAdj);
	free(mCam);

	return 0;
}



